package topoSort;

import java.awt.Color;
import java.util.*;
import java.util.Map.Entry;

import javafx.util.Pair;

public class Model extends Observable
{

	static private Integer s_nextId = new Integer(0);

	private HashMap<Integer, Set<Integer>> m_incidentList = new HashMap<Integer, Set<Integer>>();
	private Vector<HashMap<Integer, State>> m_states = new Vector<HashMap<Integer, State>>();
	private ArrayList<Integer> m_curVertex = new ArrayList<Integer>();
	private HashMap<Integer, State> m_currentState = new HashMap<Integer, State>();
	private Stack<Integer> m_currentStack = new Stack<Integer>();
	private boolean m_hasBadLink;
	private Pair<Integer, Integer> m_badLink;
	private int m_numOfMoves;
	private int m_currentMove;
	private Vector<Stack<Integer>> m_statesOfStack = new Vector<Stack<Integer>>();

	private HashMap<Integer, State> m_tempStates = new HashMap<Integer, State>();
	private Stack<Integer> m_tempStack = new Stack<Integer>();

	private void arrangeWeights()
	{
		Collection<State> states = m_currentState.values();
		Integer weight = 0;
		for (State state : states)
		{
			state.m_weight = weight++;
		}
	}

	public int verticesCount()
	{
		return m_incidentList.size();
	}

	public Integer addVertex()
	{
		if (m_currentMove != 0)
		{
			return -1;
		}
		m_incidentList.put(s_nextId, new TreeSet<Integer>());
		State state = new State(0, Color.blue);
		m_currentState.put(s_nextId, state);
		s_nextId++;
		arrangeWeights();
		setChanged();
		notifyObservers();

		return s_nextId;
	}

	/**
	 * @return set of unic identifiers of vertices
	 */
	public Set<Integer> getVeticesIds()
	{
		return m_incidentList.keySet();
	}

	/**
	 * @return return current state of stack
	 */
	public Stack<Integer> getCurrentStack()
	{
		return m_currentStack;
	}

	/**
	 * remove vertex with unique identifier id
	 * 
	 * @param id
	 *            - identifier of removable vertex
	 */
	public void removeVertex(Integer id)
	{
		for (Set<Integer> incId : m_incidentList.values())
		{
			incId.remove(id);
		}
		m_incidentList.remove(id);
		m_currentState.remove(id);
		arrangeWeights();
		setChanged();
		notifyObservers();
	}

	/**
	 * Connect with edge vertices with identifiers Sour
	 * 
	 * @param sourceId
	 * @param targetId
	 */
	public void addLink(Integer sourceId, Integer targetId)
	{
		m_incidentList.get(sourceId).add(targetId);
		setChanged();
		notifyObservers();
	}

	/**
	 * @param sourceId
	 * @param targetId
	 */
	public void reverseLink(Integer sourceId, Integer targetId)
	{
		removeLink(sourceId, targetId);
		addLink(targetId, sourceId);
		setChanged();
		notifyObservers();
	}

	/**
	 * Remove edge which connect vertices for
	 * 
	 * @param sourceId
	 * @param targetId
	 */
	public void removeLink(Integer sourceId, Integer targetId)
	{
		m_incidentList.get(sourceId).remove(targetId);
		setChanged();
		notifyObservers();
	}

	/**
	 * @return List of current state of vertices
	 */
	public HashMap<Integer, State> getCurrentState()
	{
		return m_currentState;
	}

	/**
	 * @return pair of identifiers of vertices, which connected by edge, who
	 *         participate in graph cycle
	 */
	public Pair<Integer, Integer> getBadLink()
	{
		return m_badLink;
	}

	/**
	 * @return true if cycle exist in graph, false - is not
	 */
	public boolean hasBadLink()
	{
		return m_hasBadLink;
	}

	/**
	 * Change states of vertices to next step in sort algorithm execution
	 */
	public void setNextState()
	{
		if (m_currentMove == m_numOfMoves)
		{
			return;
		}
		m_currentMove++;
		m_currentState = m_states.get(m_currentMove);
		m_currentStack = m_statesOfStack.get(m_currentMove);
		setChanged();
		notifyObservers();
	}

	/**
	 * @return number of steps in sort algorithm
	 */
	public Integer getNumOfMoves()
	{
		return m_numOfMoves;
	}

	/**
	 * Change states of vertices to first step in sort algorithm execution
	 */
	public void setFirstState()
	{
		m_currentMove = 0;
		m_currentState = m_states.get(m_currentMove);
		m_currentStack = m_statesOfStack.get(m_currentMove);
		setChanged();
		notifyObservers();
	}

	/**
	 * @return return current number of step
	 */
	public Integer getCurrentMove()
	{
		return m_currentMove;
	}

	/**
	 * Change states of vertices to last step in sort algorithm execution
	 */
	public void setLastState()
	{
		m_currentMove = m_numOfMoves;
		m_currentState = m_states.get(m_currentMove);
		m_currentStack = m_statesOfStack.get(m_currentMove);
		setChanged();
		notifyObservers();
	}

	/**
	 * Change states of vertices to previous step in sort algorithm execution
	 */
	public void setPrevState()
	{
		if (m_currentMove == 0)
		{
			return;
		}
		m_currentMove--;
		m_currentState = m_states.get(m_currentMove);
		m_currentStack = m_statesOfStack.get(m_currentMove);
		setChanged();
		notifyObservers();
	}

	/**
	 * Reset model to initial state
	 */
	public void clear()
	{
		m_incidentList.clear();
		m_states.clear();
		m_currentState.clear();
		m_currentStack.clear();
		m_hasBadLink = false;
		m_badLink = new Pair<Integer, Integer>(0, 0);
		m_numOfMoves = 0;
		m_currentMove = 0;
		m_statesOfStack.clear();
		s_nextId = 0;
		setChanged();
		notifyObservers();
	}

	/**
	 * 
	 * @param sourceId
	 * @param targetId
	 * @return true if graph has edge, whic connect vetices from sourceId to
	 *         targetId, false - if not
	 */
	public boolean hasEdge(Integer sourceId, Integer targetId)
	{
		return m_incidentList.get(sourceId).contains(targetId);
	}

	/**
	 * 
	 * @return
	 */
	public HashMap<Integer, Set<Integer>> getIncidentList()
	{
		return m_incidentList;
	}

	/**
	 * implements topologic sort algorithm
	 * 
	 * @return true if graph contain cycle, false - if is not
	 */
	@SuppressWarnings("unchecked")
	public boolean sort()
	{

		m_hasBadLink = false;
		m_numOfMoves = 0;
		m_statesOfStack.clear();
		m_states.clear();
		m_curVertex.clear();

		m_tempStates = (HashMap<Integer, State>) m_currentState.clone();
		m_tempStack = (Stack<Integer>) m_currentStack.clone();
		m_states.add((HashMap<Integer, State>) m_tempStates.clone());
		m_statesOfStack.add((Stack<Integer>) m_tempStack.clone());
		m_curVertex.add(-1);

		TreeMap<Integer, Integer> idByWeight = new TreeMap<Integer, Integer>();

		for (Entry<Integer, State> idAndWiedght : m_currentState.entrySet())
		{
			idByWeight.put(idAndWiedght.getValue().m_weight, idAndWiedght.getKey());
		}
		
		for (Integer weight : idByWeight.keySet())
		{
			Integer id = idByWeight.get(weight);
			if (m_tempStates.get(id).m_color.equals(Color.BLUE))
			{
				if (!dfs(id))
				{
					setFirstState();
					return false;
				}
			}
		}

		int newWeight = 0;
		while (!m_tempStack.empty() && !m_hasBadLink)
		{
			Integer id = m_tempStack.pop();
			// find id of vertex by it's weight
			for (Integer w : m_tempStates.keySet())
			{
				if (m_tempStates.get(w).m_weight == id
						&& !(m_tempStates.get(w).m_color.equals(Color.GREEN)))
				{
					id = w;
					break;
				}
			}
			m_numOfMoves++;
			m_curVertex.add(id);
			m_tempStates.put(id, new State(newWeight++, Color.GREEN));

			m_states.add((HashMap<Integer, State>) m_tempStates.clone());
			m_statesOfStack.add((Stack<Integer>) m_tempStack.clone());
		}

		setFirstState();
		return true;
	}

	public void swapVertexNumber(Integer v1, Integer v2)
	{
		Integer w1 = m_currentState.get(v1).m_weight;
		Integer w2 = m_currentState.get(v2).m_weight;
		int t = w1;
		m_currentState.get(v1).m_weight = w2;
		m_currentState.get(v2).m_weight = t;
		setChanged();
		notifyObservers();
		sort();
	}

	public Integer getCurrentVertexId()
	{
		if (m_currentMove >= m_curVertex.size())
		{
			return -1;
		}
		return m_curVertex.get(m_currentMove);
	}

	/**
	 * Depth-first search algrorithm participate in topologic sort
	 * 
	 * @param id
	 * @return
	 */
	@SuppressWarnings("unchecked")
	private boolean dfs(int id)
	{
		m_tempStates.put(id, new State(m_tempStates.get(id).m_weight,
				Color.GRAY));
		m_states.add((HashMap<Integer, State>) m_tempStates.clone());
		m_statesOfStack.add((Stack<Integer>) m_tempStack.clone());
		m_curVertex.add(id);
		m_numOfMoves++;

		ArrayList<Integer> incendentVerts = new ArrayList<Integer>(
				m_incidentList.get(id));
		for (int i = 0; i < incendentVerts.size(); i++)
		{
			Integer incVertId = incendentVerts.get(i);
			if (m_tempStates.get(incVertId).m_color.equals(Color.GRAY))
			{
				m_hasBadLink = true;
				m_badLink = new Pair<Integer, Integer>(id, incVertId);
				m_numOfMoves++;
				return false;
			}
			else if (m_tempStates.get(incVertId).m_color.equals(Color.BLUE))
			{
				if (!dfs(incVertId))
				{
					return false;
				}
			}
		}
		m_tempStates.put(id, new State(m_tempStates.get(id).m_weight,
				Color.BLACK));
		m_curVertex.add(id);
		m_tempStack.add(m_tempStates.get(id).m_weight);
		m_numOfMoves++;

		m_states.add((HashMap<Integer, State>) m_tempStates.clone());
		m_statesOfStack.add((Stack<Integer>) m_tempStack.clone());

		return true;
	}
}
